#include <stdio.h>
#include <stdlib.h>

int longest(int *arr,int n){
    // dp初始化
    int *dp = (int*)malloc(n * sizeof(int));

    for(int i=0;i<n;i++){
        int max_long = 1;
        for(int j=i-1;j>=0;j--){
            if(arr[i] >= dp[j] && dp[j] + 1 > max_long){
                max_long = dp[j] + 1;
            }
        }
        dp[i] = max_long;
    }
    return dp[n-1];
}

int main(){
    int arr[] = {1,4,6,2,7,14,3,1,15,17,18};
    int n = sizeof(arr)/sizeof(arr[0]);
    int result = longest(arr,n);
    printf("result: %d",result);

    return 0;
}